{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Duplicate Letters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeDuplicateLetters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #去除重复字母"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 <strong>返回结果的字典序最小</strong>（要求不能打乱其他字符的相对位置）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong><code>s = \"bcabc\"</code>\n",
    "<strong>输出<code>：</code></strong><code>\"abc\"</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong><code>s = \"cbacdcbc\"</code>\n",
    "<strong>输出：</strong><code>\"acdb\"</code></pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>该题与 1081 <a href=\"https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters\">https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters</a> 相同</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-duplicate-letters](https://leetcode.cn/problems/remove-duplicate-letters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-duplicate-letters](https://leetcode.cn/problems/remove-duplicate-letters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"bcabc\"', '\"cbacdcbc\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        seen = set()\n",
    "        remaincounter = collections.Counter(s)\n",
    "\n",
    "        for c in s:\n",
    "            if c not in seen:\n",
    "                while stack and c <stack[-1] and remaincounter[stack[-1]]>0:\n",
    "                    seen.discard(stack.pop())\n",
    "                seen.add(c)\n",
    "                stack.append(c)\n",
    "            remaincounter[c] -=1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "\n",
    "        alpha_count={}\n",
    "        stack=[]\n",
    "        for index in range(len(s)):\n",
    "            alpha_count[s[index]]=alpha_count.get(s[index],0)+1\n",
    "\n",
    "        for i in s:\n",
    "            alpha_count[i]-=1\n",
    "\n",
    "            # 栈为空\n",
    "            if i not in stack:\n",
    "                \n",
    "                while stack and ord(i)<ord(stack[-1]) and alpha_count[stack[-1]]!=0:\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "\n",
    "    \n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        ct=collections.Counter(s)\n",
    "        st=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in st:\n",
    "                ct[s[i]]-=1\n",
    "                continue\n",
    "            while st and st[-1]>s[i] and ct[st[-1]]>1:\n",
    "                ct[st[-1]]-=1\n",
    "                st.pop()\n",
    "            if s[i] not in st:st+=[s[i]]\n",
    "            else:ct[s[i]]-=1\n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        hash_map = {}\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            hash_map[ch] = hash_map.get(ch, 0) + 1\n",
    "        \n",
    "        for ch in s:\n",
    "            hash_map[ch] -= 1\n",
    "            while stack and stack[-1] >= ch and ch not in stack:\n",
    "                if hash_map.get(stack[-1], 0) == 0:\n",
    "                    break\n",
    "                stack.pop()\n",
    "            if ch not in stack:\n",
    "                stack.append(ch)\n",
    "\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        count = {}\n",
    "        for i in s:\n",
    "            if i not in count:\n",
    "                count[i] = 1\n",
    "            else:\n",
    "                count[i] +=1\n",
    "        stack =[]\n",
    "        for i in s:\n",
    "            if i not in stack:\n",
    "                while stack and count[stack[-1]]>0 and i<stack[-1]:\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "            count[i] -=1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        record = defaultdict(int)\n",
    "        for char in s:\n",
    "            record[char] += 1\n",
    "        stack = [s[0]]\n",
    "        eles = {s[0]}\n",
    "        for i in range(1, len(s)):\n",
    "            char = s[i]\n",
    "            if char in eles:\n",
    "                record[char] -= 1\n",
    "                continue\n",
    "            while stack and char <= stack[-1] and record[stack[-1]] > 1:\n",
    "                record[stack[-1]] -= 1\n",
    "                eles.remove(stack[-1])\n",
    "                stack.pop()\n",
    "            stack.append(char)\n",
    "            eles.add(char)\n",
    "\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []  #使用单调递减栈保存当前字符之前出现的非重复、并且字典序最小的字符序列\n",
    "        letter_counts = dict()\n",
    "        for ch in s:\n",
    "            if ch in letter_counts:\n",
    "                letter_counts[ch] += 1\n",
    "            else:\n",
    "                letter_counts[ch] = 1\n",
    "        for ch in s:\n",
    "            if ch not in stack:\n",
    "                # while stack and ch < stack[-1] and stack[-1] in letter_counts and letter_counts[stack[-1]] > 0:\n",
    "                while stack and ch < stack[-1] and letter_counts[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(ch)\n",
    "            letter_counts[ch] -= 1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return s \n",
    "        cntMap, isInMap = {}, {}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in cntMap:\n",
    "                cntMap[s[i]] = 0\n",
    "            cntMap[s[i]] += 1\n",
    "            if s[i] not in isInMap:\n",
    "                isInMap[s[i]] = False\n",
    "        stack = []\n",
    "        for i in range(len(s)):\n",
    "            if not isInMap[s[i]]:\n",
    "                while stack and stack[-1] > s[i]:\n",
    "                    if cntMap[stack[-1]] == 0:\n",
    "                        break\n",
    "                    isInMap[stack[-1]] = False\n",
    "                    stack.pop()\n",
    "                stack.append(s[i])\n",
    "                cntMap[s[i]] -= 1\n",
    "                isInMap[s[i]] = True\n",
    "            else:\n",
    "                cntMap[s[i]] -= 1\n",
    "        return \"\".join(stack)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        res, n = [], len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] not in res:\n",
    "                while res and s[i] < res[-1] and res[-1] in s[i+1:]:\n",
    "                    res.pop()\n",
    "                res.append(s[i])\n",
    "        return \"\".join(res)\n",
    "\n",
    "        # if len(s) == 1:\n",
    "        #     return s\n",
    "        # chars = sorted(set(s))\n",
    "        # M = {ch:set() for ch in chars}\n",
    "        # pre = {s[0]}\n",
    "        # for i in range(1,len(s)):\n",
    "        #     for ch in pre:\n",
    "        #         M[ch].add(s[i])\n",
    "        #     pre.add(s[i])\n",
    "        # Next = {ch:sorted(M[ch]) for ch in M}\n",
    "        # def backtrack(cur_ch, path):\n",
    "        #     if len(path) == len(chars):\n",
    "        #         return path[:]\n",
    "        #     for ch in Next[cur_ch]:\n",
    "        #         if ch not in path:\n",
    "        #             path.append(ch)\n",
    "        #             return backtrack(ch, path)\n",
    "        #             path.pop()\n",
    "        # for ch in chars:\n",
    "        #     if backtrack(ch, [ch]):\n",
    "        #         return \"\".join(backtrack(ch, [ch]))\n",
    "\n",
    "        # index = 0\n",
    "        # while index < len(s):\n",
    "        #     if s[index] not in res:\n",
    "        #         res.append(s[index])\n",
    "        #     else:\n",
    "        #         new = res[:]\n",
    "        #         new.remove(s[index])\n",
    "        #         new.append(s[index])\n",
    "        #         if \"\".join(new) < \"\".join(res):\n",
    "        #             res = new\n",
    "        #     index += 1\n",
    "        # return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        st = []\n",
    "        cnt = Counter(s)\n",
    "        for c in s:\n",
    "            if c not in st:\n",
    "                while st and st[-1] > c and cnt[st[-1]]:\n",
    "                    st.pop()\n",
    "                st.append(c)\n",
    "            cnt[c] -= 1\n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        visited = [0] * 256\n",
    "        cnt = Counter(s)\n",
    "        for ele in s:\n",
    "            cnt[ele] -= 1\n",
    "            if visited[ord(ele)]:\n",
    "                continue\n",
    "            while stack and ele < stack[-1] and cnt[stack[-1]]:\n",
    "                cur = stack.pop()\n",
    "                visited[ord(cur)] = 0\n",
    "            stack.append(ele)\n",
    "            visited[ord(ele)] = 1\n",
    "        return \"\".join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\r\n",
    "        d = {}\r\n",
    "        for c in s:\r\n",
    "            d[c] = d.get(c, 0) + 1\r\n",
    "        res = []\r\n",
    "        seen = set()\r\n",
    "        for c in s:\r\n",
    "            if c not in seen:\r\n",
    "                while res and d[res[-1]] > 0 and res[-1] > c:\r\n",
    "                    a = res.pop()\r\n",
    "                    seen.discard(a)\r\n",
    "                res.append(c)\r\n",
    "                seen.add(c)\r\n",
    "            d[c] = d[c] - 1\r\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        left = Counter(s)\n",
    "        ans = []\n",
    "        in_ans = set()\n",
    "        for c in s:\n",
    "            left[c] -= 1\n",
    "            if c in in_ans:\n",
    "                continue\n",
    "            while ans and c < ans[-1] and left[ans[-1]]:\n",
    "                in_ans.remove(ans.pop()) \n",
    "            ans.append(c)\n",
    "            in_ans.add(c)\n",
    "        return \"\".join(ans)           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        remain_counter = collections.Counter(s)\n",
    "\n",
    "        for ch in s:\n",
    "            if ch not in stack:\n",
    "                while stack and ch < stack[-1] and remain_counter[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(ch)\n",
    "\n",
    "            remain_counter[ch] -= 1\n",
    "        \n",
    "        return ''.join(stack)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s) -> int:\n",
    "        stack = []\n",
    "        seen = set()\n",
    "        remain_counter = collections.Counter(s)\n",
    "\n",
    "        for c in s:\n",
    "            if c not in seen:\n",
    "                while stack and c < stack[-1] and  remain_counter[stack[-1]] > 0:\n",
    "                    seen.discard(stack.pop())\n",
    "                seen.add(c)\n",
    "                stack.append(c)\n",
    "            remain_counter[c] -= 1\n",
    "        return ''.join(stack)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n==1:\n",
    "            return s\n",
    "        else:\n",
    "            stack = []\n",
    "            for i in range(n):\n",
    "                # 定义出栈条件, 如果s[i]<stack[-1], 并且stack[-1] in s[i+1::]则进行出栈操作\n",
    "                while stack and (s[i]<stack[-1]) and (stack[-1] in s[i+1::]) and (s[i] not in stack):\n",
    "                    stack.pop()\n",
    "                if s[i] not in stack:\n",
    "                    stack.append(s[i])\n",
    "            return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        numdict = {}\n",
    "        instack = {}\n",
    "        for stri in s:\n",
    "            if numdict.get(stri) == None:\n",
    "                numdict[stri] = 0\n",
    "            numdict[stri] += 1\n",
    "        for stri in s:\n",
    "            if instack.get(stri) != None:\n",
    "                numdict[stri] -= 1\n",
    "                continue\n",
    "            while stack and stack[-1] > stri and numdict.get(stack[-1]) > 0:\n",
    "                instack.pop(stack[-1])\n",
    "                stack.pop()\n",
    "            stack.append(stri)\n",
    "            instack[stri] = 1\n",
    "            numdict[stri] -= 1\n",
    "            # print(stack, stri, numdict[stri])\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        alpha_map = {}\n",
    "        used = set()\n",
    "        stk = []\n",
    "        for ch in s:\n",
    "            alpha_map[ch] = alpha_map.get(ch, 0) + 1\n",
    "        for ch in s:\n",
    "            alpha_map[ch] -= 1\n",
    "            if ch in used:\n",
    "                continue\n",
    "            while stk and stk[-1] > ch:\n",
    "                if alpha_map[stk[-1]] == 0:\n",
    "                    break\n",
    "                used.remove(stk[-1])\n",
    "                stk.pop()\n",
    "            stk.append(ch)\n",
    "            used.add(ch)\n",
    "        return \"\".join(stk)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        ret = []\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if ret and s[i] in ret:\n",
    "                continue\n",
    "            while ret and ret[-1] > s[i]:\n",
    "                if s.find(ret[-1], i) != -1:\n",
    "                    ret.pop(-1)\n",
    "                else:\n",
    "                    break\n",
    "            ret.append(s[i])\n",
    "        return ''.join(ret)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = list()\n",
    "        remain_count = Counter(s)\n",
    "        for i in s:\n",
    "            if i not in stack:\n",
    "                while stack and i < stack[-1] and remain_count[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "            remain_count[i] -= 1\n",
    "        return \"\".join(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        # 没有删除/保留次数，首先需要自己计算\n",
    "        dic = Counter(s)  # 统计字符串中各字符出现的次数\n",
    "        stack = []  # 栈，存不重复出现的字符\n",
    "        for zm in s:\n",
    "            if zm not in stack:\n",
    "                while stack and stack[-1] > zm and dic[stack[-1]] > 0:  # 确保后面存在相同字符才将前面的字符删除\n",
    "                    stack.pop()\n",
    "                stack.append(zm)\n",
    "            dic[zm] -= 1  # 字符出现一次次数-1\n",
    "        return ('').join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        cnt = collections.Counter(s)\n",
    "        stack = []\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch not in stack:\n",
    "                while stack and stack[-1] > ch and cnt[stack[-1]] >=1:\n",
    "                    stack.pop()\n",
    "                stack.append(ch)\n",
    "            cnt[ch] -= 1\n",
    "                \n",
    "        return \"\".join(stack)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        d = {}\n",
    "        num = {}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in num:\n",
    "                num[s[i]] = 1\n",
    "            else:\n",
    "                num[s[i]] = num[s[i]]+1\n",
    "        for i in range(len(s)):\n",
    "            if len(stack) == 0:\n",
    "                stack.append(s[i])\n",
    "                d[s[i]] =1\n",
    "                num[s[i]] = num[s[i]]-1\n",
    "            else:\n",
    "                if s[i] not in d or d[s[i]] == 0:\n",
    "                    while len(stack) >0 and (stack[-1]>=s[i] and num[stack[-1]]>0):\n",
    "                        c = stack.pop(-1)\n",
    "                        d[c] =0\n",
    "                    stack.append(s[i])\n",
    "                    d[s[i]] =1\n",
    "                    num[s[i]] = num[s[i]]-1\n",
    "                else:\n",
    "                    num[s[i]] = num[s[i]]-1\n",
    "                    continue    \n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        nums = Counter(s)\n",
    "        stk = []\n",
    "        for c in s:\n",
    "            nums[c] -= 1\n",
    "            if c in stk: continue \n",
    "            while stk and stk[-1] > c and nums[stk[-1]] > 0:\n",
    "                stk.pop()\n",
    "            stk.append(c) \n",
    "        return \"\".join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack: list[str] = []\n",
    "        count: dict[str, int] = {}\n",
    "        char_set: set[str] = set()\n",
    "\n",
    "        for char in s:\n",
    "            if char not in count:\n",
    "                count[char] = 1\n",
    "            else:\n",
    "                count[char] += 1\n",
    "\n",
    "        for char in s:\n",
    "            count[char] -= 1\n",
    "\n",
    "            if char in char_set:\n",
    "                continue\n",
    "\n",
    "            while stack and char < stack[-1]:\n",
    "                if count[stack[-1]] == 0:\n",
    "                    break\n",
    "\n",
    "                char_set.remove(stack.pop())\n",
    "\n",
    "            stack.append(char)\n",
    "            char_set.add(char)\n",
    "\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        d = Counter(s)\n",
    "        l = []\n",
    "        enter = [False]*26\n",
    "        for t in s:\n",
    "            if not l:\n",
    "                l.append(t)\n",
    "                enter[ord(t)-ord('a')] = True\n",
    "                d[t] -= 1\n",
    "            else:\n",
    "                if enter[ord(t)-ord('a')]:\n",
    "                    d[t] -= 1\n",
    "                else:\n",
    "\n",
    "                    while l and d[l[-1]]>0 and l[-1] >=t:\n",
    "                        enter[ord(l.pop())-ord('a')]=False\n",
    "                    if not enter[ord(t)-ord('a')]:\n",
    "                        l.append(t)\n",
    "                        enter[ord(t)-ord('a')] = True\n",
    "                    d[t] -= 1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        return \"\".join(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\r\n",
    "        d = collections.Counter(s)\r\n",
    "        used = set()\r\n",
    "        ans = []\r\n",
    "        for c in s:\r\n",
    "            if c not in used:\r\n",
    "                while ans and c < ans[-1] and d[ans[-1]] > 0:\r\n",
    "                    used.remove(ans[-1])\r\n",
    "                    ans.pop()\r\n",
    "                ans.append(c)\r\n",
    "                used.add(c)\r\n",
    "            d[c] -= 1\r\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        count = Counter(list(s))\n",
    "        rst = []\n",
    "        mem = set()\n",
    "\n",
    "        for char in s:\n",
    "            if not char in mem:\n",
    "                while len(rst) > 0 and char < rst[-1] and count[rst[-1]] > 0:\n",
    "                    mem -= {rst[-1]}\n",
    "                    rst.pop()\n",
    "\n",
    "                rst.append(char)\n",
    "                mem.add(char)\n",
    "            count[char] -= 1\n",
    "\n",
    "        return \"\".join(rst)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s) -> int:\n",
    "        stack = []\n",
    "        remain_counter = collections.Counter(s)\n",
    "\n",
    "        for c in s:\n",
    "            if c not in stack:\n",
    "                while stack and c < stack[-1] and  remain_counter[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(c)\n",
    "            remain_counter[c] -= 1\n",
    "        return ''.join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 整体思路：一个计数器计数s中各个字母出现的次数，次数>1则可以删除\n",
    "# 对于那些可以删除的字符，用单调栈保证字典序最小：递增栈\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        count = defaultdict(int)\n",
    "        for c in s:\n",
    "            count[c] += 1\n",
    "        stack = []\n",
    "        inStack = defaultdict(bool)\n",
    "        res = []\n",
    "        for c in s:\n",
    "            # if count[c] > 1:\n",
    "            if inStack[c]:   # 这时候遇到的是后边的那个c，由于前边是按照字典序最小留下来的c，所以选择后边的c字典序会变大（两个c之间的字符是比c大的，选后边的，字典序会靠后）\n",
    "                count[c] -= 1\n",
    "                continue\n",
    "            while stack and stack[-1] > c:\n",
    "                if count[stack[-1]] == 0: # 只剩下一个栈顶元素，就不能再pop出来了\n",
    "                    break\n",
    "                p = stack.pop()\n",
    "                inStack[p] = False\n",
    "            \n",
    "            stack.append(c)\n",
    "            inStack[c] = True\n",
    "            count[c] -= 1   # 从左往右遍历字符串，每次遍历到一个字符，其【剩余出现次数】减1\n",
    "        return \"\".join(stack)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in stack and (stack == [] or s[i] > stack[-1] ):\n",
    "                stack.append(s[i])\n",
    "            elif s[i] < stack[-1] and s[i] not in stack:\n",
    "                bak = stack[:]\n",
    "                for j in range(len(bak) - 1, -1, -1):\n",
    "                    if bak[j] in s[i:] and stack[j] > s[i]:\n",
    "                        stack.pop(j)\n",
    "                    else:\n",
    "                        break\n",
    "                stack.append(s[i])\n",
    "        return ''.join(stack)\n",
    "                    \n",
    "            \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        ls = len(s)\n",
    "        numr = collections.defaultdict(int)\n",
    "        visit = collections.defaultdict(bool)\n",
    "        for char in s:\n",
    "            numr[char] +=1\n",
    "        st = []\n",
    "        for char in s:\n",
    "            if not visit[char]:\n",
    "                while(st and st[-1]>char and numr[st[-1]]>0):\n",
    "                    visit[st[-1]] = False\n",
    "                    st.pop()\n",
    "                visit[char] = True\n",
    "                st.append(char)\n",
    "            numr[char] -=1 \n",
    "        return \"\".join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        remain = Counter(s)\n",
    "        for i, letter in enumerate(s):\n",
    "            if letter in stack:\n",
    "                remain[letter] -= 1\n",
    "                continue\n",
    "            while stack and stack[-1] > letter and remain[stack[-1]] > 0:\n",
    "                stack.pop()\n",
    "            stack.append(letter)\n",
    "            remain[letter] -= 1\n",
    "        return ''.join(stack)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        ret = []\n",
    "        n = len(s)\n",
    "        last = [-1] * 26\n",
    "\n",
    "        for i in range(n):\n",
    "            last[ord(s[i])-ord('a')] = i\n",
    "    \n",
    "        for i in range(n):\n",
    "            if ret and s[i] in ret:\n",
    "                continue\n",
    "            while ret and ret[-1] > s[i]:\n",
    "                if last[ord(ret[-1])-ord('a')] > i:\n",
    "                    ret.pop(-1)\n",
    "                else:\n",
    "                    break\n",
    "            ret.append(s[i])\n",
    "        return ''.join(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "\n",
    "        remain_counter = Counter(s)\n",
    "        stack = []\n",
    "        for cur_s in s:\n",
    "            if cur_s not in stack:\n",
    "                #将在cur_s之前且比它大的字母，尽可能得排除。排除不掉的是没办法\n",
    "                while (stack) and (cur_s<stack[-1]) and  (remain_counter[stack[-1]] > 0):\n",
    "                    stack.pop()\n",
    "                stack.append(cur_s)\n",
    "            remain_counter[cur_s] -= 1\n",
    "        return ''.join(stack)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stk = []\n",
    "        remain_cnt = collections.Counter(s)\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] not in stk:   #删除相同元素，堆栈中的字典序已经是最小的，后面如出现相同元素，不必在入栈，达到删除相同元素的结果\n",
    "                while stk and stk[-1] > s[i] and remain_cnt[stk[-1]]>0:\n",
    "                    stk.pop()\n",
    "                stk.append(s[i])\n",
    "            remain_cnt[s[i]] -= 1\n",
    "        return ''.join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        left = Counter(s)  # 统计每个字母的出现次数\n",
    "        ans = []\n",
    "        in_ans = set()\n",
    "        for c in s:\n",
    "            left[c] -= 1\n",
    "            if c in in_ans:  # ans 中不能有重复字母\n",
    "                continue\n",
    "            # (设 x=ans[-1]) 如果 c < x，且右边还有 x，那么可以把 x 去掉，\n",
    "            # 因为后面可以重新把 x 加到 ans 中\n",
    "            while ans and c < ans[-1] and left[ans[-1]]:\n",
    "                in_ans.remove(ans.pop())  # 标记 x 不在 ans 中\n",
    "            ans.append(c)  # 把 c 加到 ans 的末尾\n",
    "            in_ans.add(c)  # 标记 c 在 ans 中\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        count = Counter(s)\n",
    "        in_res = []\n",
    "        res = []\n",
    "        for c in s:\n",
    "            count[c] -= 1\n",
    "            if c in in_res:\n",
    "                continue\n",
    "            while res and c < res[-1] and count[res[-1]] > 0:\n",
    "                in_res.remove(res.pop())\n",
    "            res.append(c)\n",
    "            in_res.append(c)\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        d = Counter(s)\n",
    "        l = []\n",
    "        enter = [False]*26\n",
    "        for t in s:\n",
    "            if not l:\n",
    "                l.append(t)\n",
    "                enter[ord(t)-ord('a')] = True\n",
    "                d[t] -= 1\n",
    "            else:\n",
    "                if enter[ord(t)-ord('a')]:\n",
    "                    d[t] -= 1\n",
    "                else:\n",
    "\n",
    "                    while l and d[l[-1]]>0 and l[-1] >t:\n",
    "                        enter[ord(l.pop())-ord('a')]=False\n",
    "                    if not enter[ord(t)-ord('a')]:\n",
    "                        l.append(t)\n",
    "                        enter[ord(t)-ord('a')] = True\n",
    "                    d[t] -= 1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        return \"\".join(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s) -> int:\n",
    "        stack=[]\n",
    "        seen=set()\n",
    "        dic=collections.Counter(s)\n",
    "        # for c in s:\n",
    "        #     while stack and dic[stack[-1]]>0 and stack[-1]>=c:\n",
    "        #         stack.pop()\n",
    "        #     stack.append(c)\n",
    "        #     dic[c]-=1\n",
    "        # return \"\".join(stack)\n",
    "\n",
    "        ### 上述方案报错，\"cbacdcbc\" 正常应该是acdb,但是结果是acdbc,\n",
    "        ### 我们必须使用一个set来维持恒定\n",
    "\n",
    "        for c in s:\n",
    "\n",
    "            if c not in seen:\n",
    "                while stack and dic[stack[-1]]>0 and stack[-1]>=c:\n",
    "                    seen.remove(stack.pop())\n",
    "                seen.add(c)\n",
    "                stack.append(c)\n",
    "            dic[c]-=1\n",
    "        return \"\".join(stack)\n",
    "        ## 如果进来的是aaabc，你必须要使用set,不然两个a会同时进来\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # stack = []\n",
    "        # seen = set()\n",
    "        # remain_counter = collections.Counter(s)\n",
    "\n",
    "        # for c in s: ### 不能重复，所以后面出现重复直接跳过，因为前面已经有序了，不管是哪个位置重复，都不影响有序，可以跳过\n",
    "        #     if c not in seen:\n",
    "        #         while stack and c < stack[-1] and  remain_counter[stack[-1]] > 0:\n",
    "        #             seen.discard(stack.pop()) ### 全删了\n",
    "        #         seen.add(c)\n",
    "        #         stack.append(c)\n",
    "        #     remain_counter[c] -= 1\n",
    "        # return ''.join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # @ lambda _ : print(_(_, s))\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        # Count = collections.Counter(s)\n",
    "\n",
    "        Count = {}\n",
    "\n",
    "        for x in s:\n",
    "            Count[x] = Count.get(x, 0) + 1\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for c in s:\n",
    "            Count[c] -= 1\n",
    "\n",
    "            if c in stack: # stack里面不能有重复字母\n",
    "                continue\n",
    "\n",
    "            if c not in stack:\n",
    "                while (stack != [] and c < stack[-1] and Count[stack[-1]] != 0):\n",
    "                    stack.pop()\n",
    "                stack.append(c)\n",
    "        \n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        ret = []\n",
    "        n = len(s)\n",
    "        def find(ch, i):\n",
    "            for inx in range(i+1, n):\n",
    "                if s[inx] == ch:\n",
    "                    return inx\n",
    "            return -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if ret and s[i] in ret:\n",
    "                continue\n",
    "            # s.find 性能优化\n",
    "            while ret and ret[-1] > s[i]:\n",
    "                if find(ret[-1], i) != -1:\n",
    "                    ret.pop(-1)\n",
    "                else:\n",
    "                    break\n",
    "            ret.append(s[i])\n",
    "        return ''.join(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "vocab = [chr(i) for i in range(26)]\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        counter = Counter(s)   \n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in res:\n",
    "                while res and s[i] < res[-1] and counter[res[-1]] > 0:\n",
    "                    res.pop()\n",
    "                res.append(s[i])\n",
    "            counter[s[i]] -= 1\n",
    "        return ''.join(res)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        d = [0]*26\n",
    "        for t in s:\n",
    "            d[ord(t)-ord('a')] +=1\n",
    "        l = []\n",
    "        enter = [False]*26\n",
    "        for t in s:\n",
    "            if enter[ord(t)-ord('a')]:\n",
    "                d[ord(t)-ord('a')] -= 1\n",
    "            else:\n",
    "                while l and d[ord(l[-1]) - ord('a')]>0 and l[-1] >t:\n",
    "                    enter[ord(l.pop())-ord('a')]=False\n",
    "                l.append(t)\n",
    "                enter[ord(t)-ord('a')] = True\n",
    "                d[ord(t)-ord('a')] -= 1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        return \"\".join(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        n, cnt, res = len(s), Counter(), ''\n",
    "        for ch in s:\n",
    "            cnt[ch] += 1\n",
    "        stk = deque()\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch not in stk:\n",
    "                while stk and ch <= stk[-1]:\n",
    "                    top = stk[-1]\n",
    "                    if cnt[top] > 0:\n",
    "                        stk.pop()\n",
    "                    else:\n",
    "                        break\n",
    "                stk.append(ch)\n",
    "            cnt[ch] -= 1\n",
    "        while stk:\n",
    "            res += stk.popleft()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        had = Counter(s)\n",
    "        st = []\n",
    "        st_had = set()\n",
    "\n",
    "        for x in s:\n",
    "            if x in st_had:\n",
    "                had[x] -= 1\n",
    "                continue\n",
    "            while st and st[-1] >= x and had[st[-1]] > 0:\n",
    "                st_had.remove(st.pop())  \n",
    "      \n",
    "            st.append(x)\n",
    "            st_had.add(x)\n",
    "            had[x] -= 1\n",
    "        return ''.join(st)         \n",
    "\n",
    "        \n",
    "\n",
    "                     \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch not in stack:\n",
    "                while stack and ch < stack[-1] and cnt[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                stack.append(ch)\n",
    "            cnt[ch] -= 1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = list()\n",
    "        for i, value in enumerate(s):\n",
    "            if value not in stack:\n",
    "                while stack and stack[-1] > value and stack[-1] in s[i+1:]:\n",
    "                    stack.pop()\n",
    "                stack.append(value)\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters_1(self, s: str) -> str:\n",
    "        # 1. 每个字母记录需要删掉的个数\n",
    "        # 2. 记录当前已有的字母（set）\n",
    "        # 3. 如果栈顶元素(字典序)大于要入栈的元素，那么就在满足条件1的情况下，不断弹出栈顶元素，再入栈\n",
    "        # 4. 如果条件3已经满足，但2中已有记录，那么同样也不入栈\n",
    "\n",
    "        counter = {}\n",
    "        record = set()\n",
    "        for c in s:\n",
    "            if c not in counter:\n",
    "                counter[c] = 0\n",
    "            counter[c] += 1\n",
    "\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c not in record:  # key\n",
    "                while len(stack) > 0 and c < stack[-1] and counter[stack[-1]] > 0:  #  not > 1 !!!\n",
    "                    # counter[stack[-1]] -= 1\n",
    "                    if stack[-1] in record:\n",
    "                        record.remove(stack[-1])\n",
    "                    stack.pop()\n",
    "\n",
    "                record.add(c)\n",
    "                stack.append(c)\n",
    "            # if c not in record:\n",
    "            #     record.add(c)\n",
    "\n",
    "            counter[stack[-1]] -= 1  # 应该放在这里，因为如果c已经在record里，那么直接不考虑入栈操作，相当于删掉了这个字符\n",
    "\n",
    "        return \"\".join(stack)\n",
    "        \n",
    "\n",
    "    def removeDuplicateLetters(self, s) -> int:\n",
    "        stack = []\n",
    "        seen = set()\n",
    "        remain_counter = collections.Counter(s)\n",
    "\n",
    "        for c in s:\n",
    "            if c not in seen:\n",
    "                while stack and c < stack[-1] and  remain_counter[stack[-1]] > 0:\n",
    "                    seen.discard(stack.pop())\n",
    "                seen.add(c)\n",
    "                stack.append(c)\n",
    "            remain_counter[c] -= 1\n",
    "        return ''.join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import OrderedDict\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        last_occurrence = {char: i for i, char in enumerate(s)}\n",
    "        stack = []\n",
    "\n",
    "        for i, char in enumerate(s):\n",
    "            if char not in stack:\n",
    "                # 如果当前字符比栈顶字符小且栈顶字符在后面还会出现，则弹出栈顶字符\n",
    "                while stack and char < stack[-1] and i < last_occurrence[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                stack.append(char)\n",
    "\n",
    "        result = ''.join(stack)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        cnt = [0] * 26\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c in stack:\n",
    "                cnt[ord(c) - ord('a')] -= 1\n",
    "                continue\n",
    "            while stack and ord(stack[-1]) > ord(c) and cnt[ord(stack[-1]) - ord('a')] > 0:\n",
    "                stack.pop(-1)\n",
    "            stack.append(c)\n",
    "            cnt[ord(c) - ord('a')] -= 1\n",
    "        return ''.join(stack)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        remain_counter = collections.Counter(s)\n",
    "\n",
    "        for c in s:\n",
    "            if c not in stack:\n",
    "                while stack and c < stack[-1] and  remain_counter[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(c)\n",
    "            remain_counter[c] -= 1\n",
    "        return ''.join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        seen = set()\n",
    "        last_occurence = {c: i for i, c in enumerate(s)}\n",
    "        for i, c in enumerate(s):\n",
    "            if c not in seen:\n",
    "                while stack and c<stack[-1] and i<last_occurence[stack[-1]]:\n",
    "                    seen.discard(stack.pop())\n",
    "                seen.add(c)\n",
    "                stack.append(c)\n",
    "        return ''.join(stack)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        counter = {}\n",
    "        visited = set()\n",
    "        stack = []\n",
    "        for char in s:\n",
    "            if char in counter:\n",
    "                counter[char] += 1\n",
    "            else:\n",
    "                counter[char] = 1\n",
    "        for char in s:\n",
    "            counter[char] -= 1\n",
    "            if char in visited:\n",
    "                continue\n",
    "            while stack and char < stack[-1] and counter[stack[-1]] > 0:\n",
    "                visited.remove(stack.pop())\n",
    "            stack.append(char)\n",
    "            visited.add(char)\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        dict1 = collections.Counter(s)\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            dict1[i] -= 1\n",
    "            if i in stack:\n",
    "                continue\n",
    "            while stack and i < stack[-1] and dict1[stack[-1]] > 0:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return ''.join(stack)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        dic = {}\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] in dic:\n",
    "                dic[s[i]] += 1\n",
    "            else:\n",
    "                dic[s[i]] = 1\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            # 每次循环都会减少元素的实际个数\n",
    "            dic[s[i]] -= 1\n",
    "            if s[i] in st:\n",
    "                continue\n",
    "            while st and s[i] < st[-1] and dic[st[-1]] > 0:\n",
    "                j = st.pop()\n",
    "            st.append(s[i])\n",
    "        return \"\".join(st)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        n, stk, res, cnt = len(s), deque(), '', Counter()\n",
    "        for ch in s:\n",
    "            cnt[ch] += 1\n",
    "        for ch in s:\n",
    "            if ch not in stk:\n",
    "                while stk and ch <= stk[-1] and cnt[stk[-1]] > 0:\n",
    "                    stk.pop()\n",
    "                stk.append(ch)\n",
    "            cnt[ch] -= 1\n",
    "        while stk:\n",
    "            res += stk.popleft()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "vocab = [chr(i) for i in range(26)]\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        counter = Counter(s)   \n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in res:\n",
    "                while res and s[i] < res[-1] and counter[res[-1]] > 0:\n",
    "                    res.pop()\n",
    "                res.append(s[i])\n",
    "            counter[s[i]] -= 1\n",
    "        return ''.join(res)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        ret = []\n",
    "        n = len(s)\n",
    "        def find(ch, i):\n",
    "            for inx in range(i+1, n):\n",
    "                if s[inx] == ch:\n",
    "                    return inx\n",
    "            return -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(1000):\n",
    "                pass\n",
    "\n",
    "        for i in range(n):\n",
    "            if ret and s[i] in ret:\n",
    "                continue\n",
    "            # s.find 性能优化\n",
    "            while ret and ret[-1] > s[i]:\n",
    "                if find(ret[-1], i) != -1:\n",
    "                    ret.pop(-1)\n",
    "                else:\n",
    "                    break\n",
    "            ret.append(s[i])\n",
    "        return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        lastIndex = [0] * 256\n",
    "        for i, c in enumerate(s):\n",
    "            lastIndex[ord(c)] = i \n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            if c in stack:\n",
    "                continue\n",
    "            while stack and stack[-1] > c and lastIndex[ord(stack[-1])] > i:\n",
    "                stack.pop()\n",
    "            stack.append(s[i])\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        cnt = [0] * 26\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c in stack:\n",
    "                cnt[ord(c) - ord('a')] -= 1\n",
    "                continue\n",
    "            while stack and ord(stack[-1]) > ord(c) and cnt[ord(stack[-1]) - ord('a')] > 0:\n",
    "                stack.pop(-1)\n",
    "            stack.append(c)\n",
    "            cnt[ord(c) - ord('a')] -= 1\n",
    "        return \"\".join(stack)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        # 1. 每个字母记录需要删掉的个数\n",
    "        # 2. 记录当前已有的字母（set）\n",
    "        # 3. 如果栈顶元素(字典序)大于要入栈的元素，那么就在满足条件1的情况下，不断弹出栈顶元素，再入栈\n",
    "        # 4. 如果条件3已经满足，但2中已有记录，那么同样也不入栈\n",
    "\n",
    "        counter = {}  # counter记录的是每个字符的可操作次数（包括保留或删除操作）\n",
    "        record = set()\n",
    "        for c in s:\n",
    "            if c not in counter:\n",
    "                counter[c] = 0\n",
    "            counter[c] += 1\n",
    "\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            counter[c] -= 1\n",
    "            if c not in record:  # key\n",
    "                while len(stack) > 0 and c < stack[-1] and counter[stack[-1]] > 0:  #  not > 1 !!!\n",
    "                    # counter[stack[-1]] -= 1\n",
    "                    if stack[-1] in record:  # or record.discard(stack[-1])\n",
    "                        record.remove(stack[-1])\n",
    "                    stack.pop()\n",
    "\n",
    "                record.add(c)\n",
    "                stack.append(c)\n",
    "            # if c not in record:\n",
    "            #     record.add(c)\n",
    "            # counter[c] -= 1  # 放这里也可以，关键在于，不论如何操作，这个字母的可操作数都减一\n",
    "        return \"\".join(stack)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # @ lambda _ : print(_(_, s))\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        Count = collections.Counter(s)\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for c in s:\n",
    "            Count[c] -= 1\n",
    "\n",
    "            if c in stack: # stack里面不能有重复字母\n",
    "                continue\n",
    "                \n",
    "            if c not in stack:\n",
    "                while (stack != [] and c < stack[-1] and Count[stack[-1]] != 0):\n",
    "                    stack.pop()\n",
    "                stack.append(c)\n",
    "        \n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        letter_cnt = Counter(s)\n",
    "        stk = deque([])\n",
    "        appear = set()\n",
    "        for c in s:\n",
    "            if c in appear:\n",
    "                letter_cnt[c] -= 1\n",
    "                continue\n",
    "            while stk:\n",
    "                if stk[-1] > c and letter_cnt[stk[-1]] > 0:\n",
    "                    appear.discard(stk.pop())\n",
    "                else:\n",
    "                    break\n",
    "            stk.append(c)\n",
    "            appear.add(c)\n",
    "            letter_cnt[c] -= 1\n",
    "        return \"\".join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        # 存放去重的结果  \n",
    "        stk = []  \n",
    "        # 布尔数组，记录栈中是否存在某个字符  \n",
    "        # 输入字符均为 ASCII 字符，所以大小 256 够用了  \n",
    "        in_stack = [False] * 256  # 其实这个稍微有点多余，但是写了也没事\n",
    "    \n",
    "        # 维护一个计数器记录字符串中字符的数量  \n",
    "        # 因为输入为 ASCII 字符，大小 256 够用了  \n",
    "        count = [0] * 256\n",
    "        for i, c in enumerate(s):  \n",
    "            count[ord(c)] += 1  \n",
    "    \n",
    "        for c in s:  \n",
    "            # 每遍历过一个字符，都将对应的计数减一  \n",
    "            count[ord(c)] -= 1  \n",
    "    \n",
    "            if in_stack[ord(c)]: continue\n",
    "            # if c in stk: continue\n",
    "    \n",
    "            while stk and c < stk[-1]:  \n",
    "                # 若之后不存在栈顶元素了，则停止 pop  \n",
    "                if count[ord(stk[-1])] == 0:  \n",
    "                    break  \n",
    "                # 若之后还有，则可以 pop  \n",
    "                in_stack[ord(stk.pop())] = False  \n",
    "            stk.append(c)  \n",
    "            in_stack[ord(c)] = True  \n",
    "    \n",
    "        # sb = ''  \n",
    "        # while stk:  \n",
    "        #     sb += stk.pop()  \n",
    "        # return sb[::-1]\n",
    "        return ''.join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        dic = collections.Counter(s)\n",
    "        \n",
    "        for i in s:\n",
    "            if i not in stack:\n",
    "                while stack and i < stack[-1] and dic[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "            dic[i] -= 1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        remain = collections.Counter(s)\n",
    "\n",
    "        for c in s:\n",
    "            if c not in stack:\n",
    "                while stack and c < stack[-1] and remain[stack[-1]]>0:\n",
    "                    stack.pop()\n",
    "                stack.append(c)\n",
    "            remain[c] -= 1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        # stack=[]\n",
    "        # num_ch =dict()\n",
    "        # for ch in s:\n",
    "        #     if ch in num_ch:\n",
    "        #         num_ch[ch] +=1\n",
    "        #     else:\n",
    "        #         num_ch[ch] =1\n",
    "\n",
    "        # for ch in s:\n",
    "        #     if ch not in stack:\n",
    "        #         while stack and ch <stack[-1] and stack[-1] in num_ch and num_ch[stack[-1]]>0:\n",
    "        #             stack.pop()\n",
    "        #         stack.append(ch)\n",
    "        #     num_ch[ch] -=1\n",
    "        stack = []\n",
    "        letter_counts = dict()\n",
    "        for ch in s:\n",
    "            if ch in letter_counts:\n",
    "                letter_counts[ch] += 1\n",
    "            else:\n",
    "                letter_counts[ch] = 1\n",
    "\n",
    "        for ch in s:\n",
    "            if ch not in stack:\n",
    "                while stack and ch < stack[-1] and stack[-1] in letter_counts and letter_counts[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(ch)\n",
    "            letter_counts[ch] -= 1\n",
    "\n",
    "        return ''.join(stack)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        dic = {}\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] in dic:\n",
    "                dic[s[i]] += 1\n",
    "            else:\n",
    "                dic[s[i]] = 1\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            # 每次循环都会减少元素的实际个数\n",
    "            dic[s[i]] -= 1\n",
    "            # 如果小的元素存在的话,就不需要剔除(需要先判断)\n",
    "            # 实例abacb\n",
    "            if s[i] in st:\n",
    "                continue\n",
    "            while st and s[i] < st[-1] and dic[st[-1]] > 0:\n",
    "                j = st.pop()\n",
    "            st.append(s[i])\n",
    "        return \"\".join(st)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        res = []\n",
    "        counter = collections.Counter(s)\n",
    "        for c in s:\n",
    "            counter[c]-=1\n",
    "            if c not in res:\n",
    "                \n",
    "                while res and res[-1]>c and counter[res[-1]]>0:\n",
    "                    res.remove(res[-1])\n",
    "                res.append(c)                \n",
    "        return \"\".join(res)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        def char_index(c):\n",
    "            return ord(c)-ord('a')\n",
    "\n",
    "        s = list(s)\n",
    "        # 统计字数\n",
    "        remain = [0]*26\n",
    "        for c in s:\n",
    "            remain[char_index(c)] += 1\n",
    "        # print(remain)\n",
    "\n",
    "        result = []\n",
    "        in_result = [0]*26\n",
    "        l_result = 0\n",
    "        # 初始化第一个\n",
    "        c = s.pop(0)\n",
    "        i_c = char_index(c)\n",
    "        remain[i_c] -= 1\n",
    "        result.append(c)\n",
    "        in_result[i_c] = 1\n",
    "        l_result += 1\n",
    "        while s:\n",
    "            c = s.pop(0)\n",
    "            i_c = char_index(c)\n",
    "            remain[i_c] -= 1\n",
    "\n",
    "            if in_result[i_c]:  # 已经有了\n",
    "                print(c)\n",
    "                continue\n",
    "            else:\n",
    "                last_c = result[-1]\n",
    "                i_lc = char_index(last_c)\n",
    "                while i_lc > i_c and remain[i_lc] != 0:  # result 尾部可以优化\n",
    "                    result.pop(l_result-1)\n",
    "                    l_result -= 1\n",
    "                    in_result[i_lc] = 0\n",
    "                    if l_result == 0:  # 空了\n",
    "                        break\n",
    "                    else:\n",
    "                        last_c = result[l_result-1]\n",
    "                        i_lc = char_index(last_c)\n",
    "\n",
    "                result.append(c)\n",
    "                in_result[i_c] = 1\n",
    "                l_result += 1\n",
    "        \n",
    "        return ''.join(result)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        st = []\n",
    "        for ch in s:\n",
    "            if ch not in st:\n",
    "                while st and cnt[st[-1]] > 1 and ch < st[-1]:\n",
    "                    cnt[st.pop()] -= 1\n",
    "                st.append(ch)\n",
    "            else:\n",
    "                cnt[ch] -= 1\n",
    "\n",
    "        return \"\".join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        d = Counter(s)\n",
    "        l = []\n",
    "        enter = [False]*26\n",
    "        for t in s:\n",
    "            if not l:\n",
    "                l.append(t)\n",
    "                enter[ord(t)-ord('a')] = True\n",
    "                d[t] -= 1\n",
    "            else:\n",
    "                if enter[ord(t)-ord('a')]:\n",
    "                    d[t] -= 1\n",
    "                else:\n",
    "\n",
    "                    while l and d[l[-1]]>0 and l[-1] >=t:\n",
    "                        enter[ord(l.pop())-ord('a')]=False\n",
    "                    # if not enter[ord(t)-ord('a')]:\n",
    "                    l.append(t)\n",
    "                    enter[ord(t)-ord('a')] = True\n",
    "                    d[t] -= 1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        return \"\".join(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        dd = {}\n",
    "        for c in s:\n",
    "            if c in dd:\n",
    "                dd[c] += 1\n",
    "            else:\n",
    "                dd[c] = 1\n",
    "        stack = []\n",
    "        stack_set = set()\n",
    "        for c in s:\n",
    "            if c in stack_set:\n",
    "                dd[c] -= 1\n",
    "                continue\n",
    "            while len(stack) > 0 and (stack[-1] >= c and dd[stack[-1]] > 0):\n",
    "                stack_set.remove(stack[-1])\n",
    "                del stack[-1]\n",
    "            stack.append(c)\n",
    "            dd[c] -= 1\n",
    "            stack_set.add(c)\n",
    "        return \"\".join(stack)\n",
    "\n",
    "\n",
    "\n",
    "        # boolean = [True] * len(s)\n",
    "        # s_dict = dict()\n",
    "        # for i,c in enumerate(s):\n",
    "        #     if c not in s_dict:\n",
    "        #         s_dict[c] = i\n",
    "        #     else:\n",
    "        #         pre_idx = s_dict[c]\n",
    "        #         next_idx = pre_idx + 1\n",
    "        #         while next_idx is False:\n",
    "        #             next_idx += 1\n",
    "        #         if s[pre_idx] <= s[next_idx]:\n",
    "        #             boolean[i] = False\n",
    "        #         else:\n",
    "        #             boolean[pre_idx] = False\n",
    "        #             s_dict[c] = i\n",
    "        # out = []\n",
    "        # for i, b in enumerate(boolean):\n",
    "        #     if b:\n",
    "        #         out.append(s[i])\n",
    "        # return \"\".join(out)\n",
    "\n",
    "\n",
    "\n",
    "        # dd = {}\n",
    "        # for i, c in enumerate(s):\n",
    "        #     if c in dd:\n",
    "        #         dd[c].append(i)\n",
    "        #     else:\n",
    "        #         dd[c] = [i]\n",
    "        # boolean = [True] * len(s)\n",
    "        # for k, v in dd.items():\n",
    "        #     num = len(v)\n",
    "        #     if num == 1:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         found = False\n",
    "        #         for i, idx in enumerate(v):\n",
    "        #             if found:\n",
    "        #                 boolean[idx] = False\n",
    "        #             else:\n",
    "        #                 if idx == len(s)-1:\n",
    "        #                     boolean[idx] = True\n",
    "        #                 elif s[idx] == s[idx+1]:\n",
    "        #                     boolean[idx] = False\n",
    "        #                 elif s[idx] < s[idx+1]:\n",
    "        #                     found = True\n",
    "        #                     boolean[idx] = True\n",
    "        #                 elif s[idx] > s[idx+1]:\n",
    "        #                     boolean[idx] = False\n",
    "        #                     if i == num-1:\n",
    "        #                         boolean[idx] = False\n",
    "                    \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        ret = []\n",
    "        n = len(s)\n",
    "        def find(ch, i):\n",
    "            for inx in range(i+1, n):\n",
    "                if s[inx] == ch:\n",
    "                    return inx\n",
    "            return -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(10000):\n",
    "                pass\n",
    "\n",
    "        for i in range(n):\n",
    "            if ret and s[i] in ret:\n",
    "                continue\n",
    "            # s.find 性能优化\n",
    "            while ret and ret[-1] > s[i]:\n",
    "                if find(ret[-1], i) != -1:\n",
    "                    ret.pop(-1)\n",
    "                else:\n",
    "                    break\n",
    "            ret.append(s[i])\n",
    "        return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        c2i = Counter(s)\n",
    "        stack = []\n",
    "        bmap = set()\n",
    "        for c in s:\n",
    "            if c in bmap:\n",
    "                c2i[c]-=1\n",
    "                continue \n",
    "            while len(stack)>0 and stack[-1]>=c:\n",
    "                if c2i[stack[-1]]==0:\n",
    "                    break\n",
    "                tc = stack.pop()\n",
    "                bmap.remove(tc)\n",
    "            stack.append(c)\n",
    "            c2i[c]-=1\n",
    "            bmap.add(c)\n",
    "\n",
    "        \n",
    "        return \"\".join(stack)     \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        d = {}\n",
    "        v = {}\n",
    "        for i in s:\n",
    "            if i not in v:\n",
    "                v[i] = 0\n",
    "            v[i] += 1\n",
    "            d[i] = 0\n",
    "        ll = []\n",
    "        for i in s:\n",
    "            if d[i] == 1:\n",
    "                v[i] -= 1\n",
    "                continue \n",
    "            while ll:\n",
    "                if i < ll[-1] and v[ll[-1]] > 0:\n",
    "                    d[ll[-1]] = 0\n",
    "                    ll.pop()\n",
    "                else:\n",
    "                    break\n",
    "            d[i] = 1\n",
    "            v[i] -= 1\n",
    "            ll.append(i)\n",
    "        return \"\".join(ll)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateLetters(self, s: str) -> str:\n",
    "        stack = []\n",
    "        count = [0] * 256\n",
    "        in_stack = [False] * 256\n",
    "        for c in s:\n",
    "            count[ord(c)] += 1\n",
    "        for c in s:\n",
    "            count[ord(c)] -= 1\n",
    "            if in_stack[ord(c)]:\n",
    "                continue\n",
    "            while stack and ord(c) < ord(stack[-1]):\n",
    "                if count[ord(stack[-1])] == 0:\n",
    "                    break\n",
    "                in_stack[ord(stack.pop())] = False\n",
    "            stack.append(c)\n",
    "            in_stack[ord(c)] = True\n",
    "        return ''.join(stack)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
